# 给你一个 互不相同 的整数数组，其中 locations[i] 表示第 i 个城市的位置。
# 同时给你 start，finish 和 fuel分别表示出发城市、目的地城市和你初始拥有的汽油总量：
#
#  每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足 j != i 且 0 <= j < locations.length ，并移动到城市 j 。
#  从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|，|x| 表示 x 的绝对值。
#  请注意， fuel 任何时刻都 不能 为负，且你 可以 经过任意城市超过一次（包括 start 和 finish ）。
#  请你返回从 start 到 finish 所有可能路径的数目。
#  由于答案可能很大， 请将它对 10^9 + 7 取余后返回。
#
#  示例 1：
# 输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
# 输出：4
# 解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
# 1 -> 3
# 1 -> 2 -> 3
# 1 -> 4 -> 3
# 1 -> 4 -> 2 -> 3
#
#  示例 2：
# 输入：locations = [4,3,1], start = 1, finish = 0, fuel = 6
# 输出：5
# 解释：以下为所有可能的路径：
# 1 -> 0，使用汽油量为 fuel = 1
# 1 -> 2 -> 0，使用汽油量为 fuel = 5
# 1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
# 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
# 1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5
#
#  示例 3：
# 输入：locations = [5,2,1], start = 0, finish = 2, fuel = 3
# 输出：0
# 解释：没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。
from functools import lru_cache
from typing import List


class Solution:
    def countRoutes3(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        """
        dp[i][j]表示总油耗为 i，到达目的城市为 j 的路径数
        :param locations:
        :param start:
        :param finish:
        :param fuel:
        :return:
        """
        res, totalCity, MOD = 0, len(locations), 10 ** 9 + 7
        dp = [[0] * totalCity for _ in range(fuel + 1)]
        dp[0][start] = 1  # 起点位置不需要油耗(初始化状态)
        for usedFuel in range(fuel):
            for curCity in range(totalCity):
                if dp[usedFuel][curCity] > 0:
                    for nextCity in range(totalCity):
                        if nextCity != curCity:  # 不能选择当前城市作为下一个到达的城市
                            cost = abs(locations[nextCity] - locations[curCity])  # 计算到下一个城市所需的油耗
                            if usedFuel + cost <= fuel:  # 从当前城市到下一个城市总油耗不超过总油量，要更新状态
                                dp[usedFuel + cost][nextCity] = \
                                    (dp[usedFuel + cost][nextCity] + dp[usedFuel][curCity]) % MOD

        for i in range(fuel + 1):  # 汇总所有不超过总油量能到达finish的结果
            res = (res + dp[i][finish]) % MOD
        return res % MOD

    def countRoutes2(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        """
        记忆化搜索
        f[curPos][rest] 表示当前位于 curPos 城市，剩余的汽油量为 rest 时，到达终点 finish 的可能的路径总数
        :param locations:
        :param start:
        :param finish:
        :param fuel:
        :return:
        """
        n = len(locations)

        @lru_cache(None)
        def dfs(curPos: int, rest: int) -> int:
            if abs(locations[curPos] - locations[finish]) > rest:
                return 0
            res = 0
            for nextCity, loc in enumerate(locations):
                if curPos != nextCity:
                    cost = abs(locations[curPos] - loc)
                    if cost <= rest:
                        res += dfs(nextCity, rest - cost)
            if curPos == finish:
                res += 1
            return res % (10 ** 9 + 7)

        return dfs(start, fuel)

    def countRoutes1(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        """
        解法一：回溯(超时)
        :param locations:
        :param start:
        :param finish:
        :param fuel:
        :return:
        """
        res, totalCity = 0, len(locations)

        def dfs(curCityIndex: int, remainFuel: int) -> None:
            if remainFuel < 0:  # 没有油了，退出递归
                return
            if curCityIndex == finish:  # 到达了目的城市，说明当前尝试的路径可行
                nonlocal res
                res += 1

            for nextIndex in range(totalCity):  # 出发到下一个城市
                if nextIndex != curCityIndex:
                    dfs(nextIndex, remainFuel - abs(locations[curCityIndex] - locations[nextIndex]))

        dfs(start, fuel)
        return res % (10 ** 9 + 7)

    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        return self.countRoutes3(locations, start, finish, fuel)


if __name__ == "__main__":
    locations, start, finish, fuel = [2, 3, 6, 8, 4], 1, 3, 5
    # locations, start, finish, fuel = [4, 3, 1], 1, 0, 6
    # locations, start, finish, fuel = [5, 2, 1], 0, 2, 3
    # locations, start, finish, fuel = [2, 1, 5], 0, 0, 3
    print(Solution().countRoutes(locations, start, finish, fuel))
